<!DOCTYPE html>
<html lang="zh">

<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <title>
    
    函数的递归调用 - DSRBLOG
    
  </title>
  

  
  
  <link href="atom.xml" rel="alternate" title="DSRBLOG" type="application/atom+xml">
  <link rel="stylesheet" href="asset/css/style.min.css">
  <link rel="stylesheet" href="asset/css/doc.css">
  <script src="asset/app.js"></script>


</head>

<body> <section class="ct-body">
	<div class="container">
		<div class="columns is-variable bd-klmn-columns is-4 is-centered">
			<div class="column is-four-fifths">
				<div class="post-body single-content">
					
					<h1 class="title">
						函数的递归调用
					</h1>


					<div class="media">
						
						
						<div class="media-content">
							<div class="content">
								<p>
									<span class="date">2022/01/19 21:19 下午</span>
									

									

									<br />
									<span class="tran-tags">Tags:</span>&nbsp;
									
									<a class="tag is-link is-light">#C语言</a>
									

								</p>
							</div>
						</div>

					</div>
				</div>
				<article class="markdown-body single-content">
					<ul>
<li>在调用一个函数的过程中又出现直接或间接地调用该函数本身，称为函数的递归调用。</li>
</ul>
<h3><a id="%E4%BE%8B" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>例</h3>
<p>有五个人坐在一起，第一个人10岁，之后每一个人都比上一个人大2岁，请问第五个人多大</p>
<pre class="line-numbers"><code class="language-c">#include &lt;stdio.h&gt;

int main()
{
    int age(int n); //函数的声明；
    printf(&quot;%d&quot;, age(5));
    return 0;
}

int age(int n) //函数的定义
{
    if (n == 1)
        return 10;
    else
        return age(n - 1) + 2; //递归调用
}
</code></pre>
<h3><a id="%E4%BE%8B" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>例</h3>
<p>求n!（阶乘<code>1*2*3*4...*n = n!</code>）</p>
<pre class="line-numbers"><code class="language-c">#include &lt;stdio.h&gt;

int main()
{
    long f(int n); //声明fact()函数
    int n;
    long fact = 0;                //变量fact用来存储n!的值
    scanf(&quot;%d&quot;, &amp;n);              //输入n
    fact = f(n);                  //调用fact()函数，求出n!
    printf(&quot;%d!=%ld\n&quot;, n, fact); //输出n!
    return 0;
}

//方法一
long f(int n) //定义fact()函数
{
    int i;
    long s = 1;
    for (i = 1; i &lt;= n; i++)
        s = s * i;
    return s;
}

//方法二
long f(int n) //定义fact()函数
{
    long s;
    if (n == 0 || n == 1) //0!和1!等于0
        s = 1;
    else
        s = f(n - 1) * n; //递归调用f()函数
    return s;
}
</code></pre>
<h3><a id="%E9%80%92%E5%BD%92%E5%85%B8%E5%9E%8B%E4%BE%8B%E5%AD%90hanoi%EF%BC%88%E6%B1%89%E8%AF%BA%EF%BC%89%E5%A1%94%E9%97%AE%E9%A2%98" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>递归典型例子 -- Hanoi（汉诺）塔问题</h3>
<p>     古印度有一个梵塔，塔内有3个柱子A、B、C，开始时A柱上套有64个盘子，盘子大小不等，大的在下，小的在上。</p>
<p>    有一个老和尚想把这64个盘子从A柱移到C柱，但规定每次只能移动一个盘，且在任何时候3个柱上的盘子都是大盘在下，小盘在上，在移动过程中可以利用B柱。</p>
<p>     现在利用计算机来模拟移动盘子的过程，要求输出移动盘子的每一步。</p>
<h4><a id="%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>分析</h4>
<h5><a id="%E5%B0%86n%E4%B8%AA%E7%9B%98%E5%AD%90%E4%BB%8Ea%E6%9F%B1%E7%A7%BB%E5%8A%A8%E5%88%B0c%E6%9F%B1%E5%8F%AF%E5%88%86%E8%A7%A3%E4%B8%BA%E4%BB%A5%E4%B8%8B%E4%B8%89%E4%B8%AA%E6%AD%A5%E9%AA%A4" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>将n个盘子从A柱移动到C柱可分解为以下三个步骤</h5>
<ul>
<li>将A柱上n-1个盘借助C柱先移到B柱上</li>
<li>把A柱上剩下的一个盘移到C柱上</li>
<li>将n-1个盘从B柱借助于A柱移动到C柱上</li>
</ul>
<pre class="line-numbers"><code class="language-C">#include &lt;stdio.h&gt;

int main()
{
   void hanoi(int n, char one, char two, char three);//声明hanoi()函数
   int m;
   printf(&quot;m = &quot;);
   scanf(&quot;%d&quot;, &amp;m);
   hanoi(m, 'A', 'B', 'C');//调用hanoi()函数
   return 0;
}

void hanoi(int n, char one, char two, char three)//定义hanoi()函数
{
   if (n == 1)
       printf(&quot;%c --&gt; %c\n&quot;, one, three);
   else
   {
       hanoi(n - 1, one, three, two);
       printf(&quot;%c --&gt; %c\n&quot;, one, three);
       hanoi(n - 1, two, one, three);
   }
}
</code></pre>

				</article>
				<div class="comments-wrap">
					<div class="share-comments">
						

						

						
					</div>
				</div><!-- end comments wrap -->
			</div>
		</div><!-- end columns -->
	</div><!-- end container -->
</section>  














<script src="asset/prism.js"></script>









</body>

</html>